package problems.daily;

import java.util.Arrays;

/**
 * 2386. 找出数组第 K 大和
 *
 * @author habitplus
 * @version: 1.0
 * @history: create by guan at 2024/3/9 10:21
 */
public class DT2386 {
    int cnt;
    public long kSum(int[] nums, int k) {
        if (nums == null || nums.length < 1) {
            return 0;
        }

        int n = nums.length;
        long total = 0;
        long total2 = 0;

        for (int i = 0; i < n; ++i) {
            if (nums[i] < 0) {
                nums[i] = -nums[i];
            } else {
                total += nums[i];
            }
            total2 += Math.abs(nums[i]);
        }

        Arrays.sort(nums);

        long left = 0, right = total2;

        while (left <= right) {
            long mid = (left + right) / 2;
            cnt = 0;
            dfs(nums, k, n, 0, 0, mid);
            if (cnt < k - 1) {
                left = mid +1;
            } else {
                right = mid - 1;
            }
        }

        return total - left;
    }

    private void dfs(int[] nums, int k, int n, int i, long t, long limit) {
        if (i == n || cnt > k - 1 || t + nums[i] > limit) {
            return;
        }

        ++cnt;

        dfs(nums, k, n, i + 1, t + nums[i], limit);
        dfs(nums, k, n, i + 1, t, limit);
    }
}
